# 题目
# 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

#
# 输入：1->2->4, 1->3->4
# 输出：1->1->2->3->4->4

# 先定义节点
class Node(object):
    def __init__(self, val, p=0):
        self.data = val
        self.next = p


# 在定义单链表
class LinkList:
    def __init__(self):
        self.head = 0

    def initlist(self, data):
        self.head = Node(data[0])
        p = self.head
        for i in data[1:]:
            node = Node(i)
            p.next = node
            p = p.next


class Solution:
    def merge_two_linklist(self, l1, l2):
        head  = LinkList()
        head.initlist([0])
        temp = head

        while l1 and l2:
            if l1. < l2.val:
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next
            temp = temp.next
        temp.next = l1 if l1 else l2
        return head.next

    def main(self):
        l1 = l2 = LinkList()
        l1.initlist([1, 2, 4])
        l2.initlist([1, 3, 4])
        res = self.merge_two_linklist(l1, l2)
        print(res)


if __name__ == '__main__':
    Solution().main()
